import unittest
def fib1(n):
    "8.1"
    if n<=2:
        return 1
    return fib1(n-1)+fib1(n-2)

memo = {}
def fib2(n):
    "8.1 memoized"
    if n<=2:
        return 1
    if n in memo:
        return memo[n]
    res=fib1(n-1)+fib1(n-2)
    memo[n]=res
    return res

def fib3(n):
    "8.1"
    if n<=2:
        return 1
    preFirst=1
    preSec=1
    for i in xrange(n-2):
        tmp=preFirst+preSec
        preSec=preFirst
        preFirst=tmp
    return preFirst


class TestFibonacci(unittest.TestCase):
    inputs = ((1,1),
              (2,1),
              (3,2),
              (4,3),
              (5,5)
              )
    
    def testInputs(self):
        for inp,res in self.inputs:
            self.assertEqual(fib1(inp),res)
            self.assertEqual(fib2(inp),res)
            self.assertEqual(fib3(inp),res)



        
        
        